package com.tgy.algorithm._经典题目01;

/**
 * 给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器请返回容器能装多少水
 * 比如，arr={3，1，2，5，2，4}，根据值画出的直方图就是容器形状，该容器可以装下5格水
 * 再比如，arr={4，5，1，3，2}，该容器可以装下2格水
 */
public class _011_一维接水问题 {

    public static int rainWater(int[] nums) {

        if (nums == null || nums.length <= 2) {
            return 0;
        }

        int len = nums.length;

        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
//        leftMax[1] = nums[0];
        leftMax[0] = Integer.MIN_VALUE;
        leftMax[1] = nums[0];

        rightMax[len - 2] = nums[len - 1];
        rightMax[len - 1] = Integer.MIN_VALUE;

        // 3
        for (int i = 1; i < len; i++) {
            int lastIndex = len - i - 1;
           leftMax[i] = Math.max(nums[i - 1],leftMax[i - 1]);
           rightMax[lastIndex] = Math.max(nums[lastIndex+1],rightMax[lastIndex+1]);
        }

        int water = 0;
        for (int i = 1; i < len - 1; i++) {
            int value = Math.min(leftMax[i],rightMax[i]) - nums[i];
            if (value > 0) {
                water+= value;
            }
        }

        return water;
    }


    public static int rainWater01(int[] nums) {

        if (nums == null || nums.length <= 2) {
            return 0;
        }
        int len = nums.length;
        int left = 1;
        int right = len - 2;
        int leftMax = nums[0];
        int rightMax = nums[len - 1];
        int water = 0;
        while (left <= right) {
            if (leftMax < rightMax) {

                int value = leftMax - nums[left];
                if (value > 0) {
                    water += value;
                }
                leftMax = Math.max(leftMax,nums[left]);
                left++;
            }else {
                int value = rightMax - nums[right];
                if (value > 0) {
                    water += value;
                }
                rightMax = Math.max(rightMax,nums[right]);
                right--;
            }
        }

        return water;
    }

    public static void main(String[] args) {
//        int[] nums = {3,1,2,5,2,4};
        int[] nums = {4,5,1,3,2};
//        int water = rainWater(nums);
        int water = rainWater01(nums);
        System.out.println(water);
    }
}
